package code.D1220;

import java.util.HashMap;
import java.util.Map;

/**
 * author： yeswater
 * create： 2023/12/22
 *
 * 打家劫舍 III
 *
 */
public class T337 {
    Map<TreeNode, Integer> map = new HashMap<>();
    
    public int rob(TreeNode root) {
        // root 为第一层
        if(root==null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        int money = root.val;
        if(root.left != null){
            money += rob(root.left.left) + rob(root.left.right);
        }
        if(root.right != null){
            money += rob(root.right.left) + rob(root.right.right);
        }
        // root 的下一层为第一层
        int res = Math.max(money, rob(root.left) + rob(root.right));
        map.put(root, res);
        return res;
    }
    
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode() {
        }
        
        TreeNode(int val) {
            this.val = val;
        }
        
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
